package leetcode.lt100;

import java.util.Arrays;
import java.util.Stack;
import java.util.stream.Collectors;

class Solution_85 {

    public static void main(String[] args) {
//        int[] heights = new int[]{2, 1, 5, 6, 2, 3};
        char[][] heights = {
                {'1', '0', '1', '0', '0'},
                {'1', '0', '1', '1', '1'},
                {'1', '1', '1', '1', '1'},
                {'1', '0', '0', '1', '0'}
        };
        for (int i = 0; i < heights.length; i++) {
            System.out.println(Arrays.stream(getHeights(heights, i)).mapToObj(String::valueOf).collect(Collectors.joining("|")));
        }
        System.out.println(maximalRectangle(heights));
    }

    public static int maximalRectangle(char[][] matrix) {
        int height = matrix.length;
        int max = 0;
        for (int i = 0; i < height; i++) {
            int[] heights = getHeights(matrix, i);
            max = Math.max(max, largestRectangleArea(heights));
        }
        return max;
    }

    private static int largestRectangleArea(int[] heights) {
        int[] newHeights = new int[heights.length + 2];
        int length = newHeights.length;

        for (int i = 1; i < length - 1; i++) {
            newHeights[i] = heights[i - 1];
        }
        newHeights[0] = -1;
        newHeights[length - 1] = -1;

        Stack<Integer> stack = new Stack<>();
        int max = 0;
        for (int i = 0; i < length; i++) {
            while (!stack.empty() && newHeights[i] < newHeights[stack.peek()]) {
                Integer cur = stack.pop();
                max = Math.max(max, newHeights[cur] * (i - stack.peek() - 1));
            }
            stack.push(i);
        }
        return max;
    }

    private static int[] getHeights(char[][] matrix, int index) {
        int weight = matrix[0].length;
        int[] heights = new int[weight];
        for (int i = 0; i < weight; i++) {
            for (int j = index; j >= 0; j--) {
                if (matrix[j][i] == '1') {
                    heights[i]++;
                } else {
                    break;
                }
            }
        }
        return heights;
    }

}